package leetcode.lt100;

class Solution_60 {

	public static void main(String[] args) {

		new Solution_60().getPermutation(3, 2);
	}

	public String getPermutation(int n, int k) {
		StringBuffer sb = new StringBuffer();

		int currentK = k;
		int currentN = n - 1;
		int index;
		boolean[] used = new boolean[n];

		for (int i = 0; i < n; i++) {
			if(currentN==0){
				sb.append(get(used, 1));
				break;
			}
			index = currentK / cn(currentN);
			if (index * cn(currentN) != currentK) {
				index ++ ;
			}
			sb.append(get(used, index));
			currentK = currentK % cn(currentN);
			currentN--;
		}

		return sb.toString();
	}

	private int get(boolean[] used, int index) {
		int l = used.length;
		int count = 0;
		for (int i = 0; i < l; i++) {
			if (!used[i]) {
				count++;
			}
			if (count == index) {
				used[i] = true;
				return i + 1;
			}
		}
		return 0;
	}

	private int cn(int n) {
		int temp = n - 1;
		while (temp > 0) {
			n *= temp;
			temp--;
		}
		return n;
	}
}